/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root)return true;

    let node1 = root.left,
        node2 = root.right,
        stack1 = [],
        stack2 = [];

    //使用栈保存历史，确定好pop、push的时机
    while(node1&&node2){
        if((!node1.left&&node2.right)||(node1.left&&!node2.right)){
            return false;
        }
        if((!node1.right&&node2.left)||(node1.right&&!node2.left)){
            return false;
        }

        if(node1.val!==node2.val)return false;

        if(!node1.left&&!node2.left&&!node1.right&&!node2.right&&stack1.length>0&&stack2.length>0){
            node1 = stack1.pop().right;
            node2 = stack2.pop().left;
            while(!node1&&!node2&&stack1.length>0&&stack2.length>0){

                node1 = stack1.pop().right;
                node2 = stack2.pop().left;
            }
        }else{

            stack1.push(node1);
            stack2.push(node2);

            node1 = node1.left;
            node2 = node2.right;

            while(!node1&&!node2&&stack1.length>0&&stack2.length>0){

                node1 = stack1.pop().right;
                node2 = stack2.pop().left;
            }
        }
        //console.log(node1,node2);
    }
    //console.log(node1,node2);

    if((!node1&&node2)||(node1&&!node2))return false;

    return true;

};